package sort;

/**
 * 堆排序
 */

/**
 * 时间复杂度：O(N*logN)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 */
public class HeapSort implements ISort{
    /**
     * 创建大根堆
     * @param array
     */
    private void createHeap(int[] array) {
        for(int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
            softDown(array,i);
        }
    }
    private void softDown(int[] arr, int parent) {
        int child = parent * 2 + 1;
        while(child < arr.length) {
            if(child + 1 < arr.length && arr[child] < arr[child + 1]) {
                child += 1;
            }
            if(arr[child] > arr[parent]) {
                Swap.swap(arr,child,parent);
            }
            parent = child;
            child = parent * 2 + 1;
        }
    }

    private void softDown(int[] arr,int parent,int end) {
        int child = parent * 2 + 1;
        while(child <= end) {
            if(child + 1 <= end && arr[child] < arr[child + 1]) {
                child += 1;
            }
            if(arr[child] > arr[parent]) {
                Swap.swap(arr,child,parent);
            }
            parent = child;
            child = parent * 2 + 1;
        }
    }
    @Override
    public void sort(int[] array) {
        createHeap(array);
        for(int i = array.length - 1; i >= 0; i--) {
            Swap.swap(array,0,i);
            softDown(array,0,i-1);
        }
    }
}
